#include<bits/stdc++.h>
using namespace std;
int t,n,a[200005],o[1000005],ans,vis[2005][2005],b[200005];
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
    return;
}
void dfs(int p,int x,int y,int s){
    if(p==n+1){
        ans=max(ans,s);
        return;
    }
    if(s+b[p]<=ans)
        return;
    if(s<=vis[x][y])
        return;
    vis[x][y]=s;
    if(a[x]==a[p])
        dfs(p+1,p,y,s+a[p]);
    else dfs(p+1,p,y,s);
    if(a[y]==a[p])
        dfs(p+1,x,p,s+a[p]);
    dfs(p+1,x,p,s);
    return;
}
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    t=read();
    a[0]=0;
    int x;
    while(t--){
        n=read();
        for(register int i=1;i<=n;++i)
            a[i]=read();
        if(n>=2000){
            for(register int i=1;i<=n;++i){
                b[a[i]]++;
                if(b[a[i]]>=2){
                    ans+=a[i];
                }
            }
            write(ans);
            putchar('\n');
            continue;
        }
        ans=0;
        b[n+1]=0;
        for(register int i=n;i>=0;--i){
            b[i]=b[i+1]+a[i];
            for(register int j=0;j<=n;++j)
                vis[i][j]=-1;
        }
        dfs(1,0,0,0);
        write(ans);
        putchar('\n');
    }
    return 0;
}
